LeetCode 82、删除排序链表中的重复元素 II（递归版）

一、题目描述

给定一个已排序的链表的头 head ， 删除原始链表中所有重复数字的节点，只留下不同的数字 。返回 已排序的链表 。

二、题目解析

三、参考代码

1、Java 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/submissions/
class Solution {
    public ListNode deleteDuplicates(ListNode head) {

        // 递归终止条件
        if(head == null || head.next == null){
            return head;
        }

        // 在访问过程中，会出现两种情况
        // 1、如果访问的节点值和下一个节点值不相同
        if(head.val != head.next.val){

            // 那么说明当前访问的节点 head 需要保留下来，它和后面经过删除操作的链表连接起来

            // a、利用递归，获取后续删除了链表重复元素的链表
            ListNode resNode = deleteDuplicates(head.next);

            // 将 head 和后续已经删除了重复元素的链表连接起来
            head.next = resNode;

            // 返回这个结果就行
            return head;

        // 2、如果访问的节点值和下一个节点值相同
        }else{

            // 那说明 head 这个节点就不应该留下来

            // 现在的目的就是去找出和 head 这个节点值不一样的节点来
            ListNode newNode = head.next;

            // 利用 while 循环，找出和 head 这个节点值不一样的节点来
            while(newNode != null && head.val == newNode.val){
                newNode = newNode.next;
            }

            // 此时，经过 while 循环后，newNode 指向了一个不等于 head 的节点
            // 递归调用 deleteDuplicates 函数，处理后面的所有节点
            // 处理好后
            // 1、要么是直接是最终的结果
            // 2、要么是这个结果链表会连接在某个节点后面，比如上述的 a 操作这行代码
            return deleteDuplicates(newNode);

        }

    }
}

**2、**C++ 代码

// 登录 AlgoMooc 官网获取更多算法图解
// https://www.algomooc.com
// 作者：程序员吴师兄
// 代码有看不懂的地方一定要私聊咨询吴师兄呀
// https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/submissions/
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        // 递归终止条件
        if(head == NULL || head->next == NULL){
            return head;
        }

        // 在访问过程中，会出现两种情况
        // 1、如果访问的节点值和下一个节点值不相同
        if(head->val != head->next->val){

            // 那么说明当前访问的节点 head 需要保留下来，它和后面经过删除操作的链表连接起来

            // a、利用递归，获取后续删除了链表重复元素的链表
            ListNode *resNode = deleteDuplicates(head->next);

            // 将 head 和后续已经删除了重复元素的链表连接起来
            head->next = resNode;

            // 返回这个结果就行
            return head;

        // 2、如果访问的节点值和下一个节点值相同
        }else{

            // 那说明 head 这个节点就不应该留下来

            // 现在的目的就是去找出和 head 这个节点值不一样的节点来
            ListNode *newNode = head->next;

            // 利用 while 循环，找出和 head 这个节点值不一样的节点来
            while(newNode != NULL && head->val == newNode->val){
                newNode = newNode->next;
            }

            // 此时，经过 while 循环后，newNode 指向了一个不等于 head 的节点
            // 递归调用 deleteDuplicates 函数，处理后面的所有节点
            // 处理好后
            // 1、要么是直接是最终的结果
            // 2、要么是这个结果链表会连接在某个节点后面，比如上述的 a 操作这行代码
            return deleteDuplicates(newNode);

        }

    }
};

3、Python 代码

# 登录 AlgoMooc 官网获取更多算法图解
# https://www.algomooc.com
# 作者：程序员吴师兄
# 代码有看不懂的地方一定要私聊咨询吴师兄呀
# https://leetcode-cn.com/problems/remove-duplicates-from-sorted-list-ii/submissions/
class Solution:
    def deleteDuplicates(self, head: ListNode) -> ListNode:
        # 递归终止条件
        if head == None or head.next == None:
            return head
        

        # 在访问过程中，会出现两种情况
        # 1、如果访问的节点值和下一个节点值不相同
        if head.val != head.next.val:

            # 那么说明当前访问的节点 head 需要保留下来，它和后面经过删除操作的链表连接起来

            # a、利用递归，获取后续删除了链表重复元素的链表
            resNode = self.deleteDuplicates(head.next)

            # 将 head 和后续已经删除了重复元素的链表连接起来
            head.next = resNode

            # 返回这个结果就行
            return head

        # 2、如果访问的节点值和下一个节点值相同
        else:

            # 那说明 head 这个节点就不应该留下来

            # 现在的目的就是去找出和 head 这个节点值不一样的节点来
            newNode = head.next

            # 利用 while 循环，找出和 head 这个节点值不一样的节点来
            while newNode != None and head.val == newNode.val:
                newNode = newNode.next
            

            # 此时，经过 while 循环后，newNode 指向了一个不等于 head 的节点
            # 递归调用 deleteDuplicates 函数，处理后面的所有节点
            # 处理好后
            # 1、要么是直接是最终的结果
            # 2、要么是这个结果链表会连接在某个节点后面，比如上述的 a 操作这行代码
            return self.deleteDuplicates(newNode)

四、复杂度分析

• 时间复杂度：O(n)，其中 n 是链表的长度。
• 空间复杂度：O(n)。